# -*- coding: utf-8 -*-

''' 
Autores: 
Pedro Godinho - 6355
Pedro Lopes - 9850
'''

import sys
import math
from random import uniform
import time
import matplotlib.pyplot as plt

''' Class responsable for MergeSort algorithm and tests'''
class MergeSort:

    '''@param A: list to sort'''
    def mergesort(self,A):
        def merge(self,A,p,q,r):
            L1 = A[p:q + 1]
            L2 = A[q + 1:r + 1]
            len1 = len(L1)
            len2 = len(L2)
            i1 = 0
            i2 = 0
            i = p
            for i in range(p,r+1):
                if i2 >= len2:
                    A[i] = L1[i1]
                    i1 += 1
                elif i1 >= len1 or L2[i2] < L1[i1]:
                    A[i] = L2[i2]
                    i2 += 1
                else:
                    A[i] = L1[i1]
                    i1 += 1

        def merge_sort(self,A,p,r):
            if p < r:
                q = (int) (math.floor((p + r) / 2))
                merge_sort(self,A,p,q)
                merge_sort(self,A,q+1,r)
                merge(self,A,p,q,r)
        merge_sort(self,A,0,len(A)-1)

    def grafico(self):
        Z = [1] + range(50, 1050, 50)
        T = []
        M = 50
        for n in Z:
            A = [ uniform(0.00,1.0) for k in xrange(n)]
            tempos = []
            for k in range(M):
                t1 = time.time()
                self.mergesort(A)
                t2 = time.time()
                tempos.append(t2-t1)
            media = reduce(lambda x, y: x + y, tempos) / len(tempos)
            var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
        
            T.append((n,media, var))

        X = [n for n, media, var in T]
        Y = [media for n, media, var in T]
        ct = 10e5
        Z = [ (n * (math.log(n)))/ct for n, media, var in T]


        plt.grid(True)
        plt.ylabel(u'T(n) - tempo de execução médio em segundos')
        plt.xlabel(u'n - número de elementos')
        plt.plot(X,Y,'rs', label="resultado experimental")
        plt.plot(X, Z, 'b^', label=u"previsão teórica")
        plt.title("Merge Sort")
        plt.legend()
        plt.show()
